//给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
// 
//
// 如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
//输出："apple"
// 
//
// 示例 2： 
//
// 
//输入：s = "abpcplea", dictionary = ["a","b","c"]
//输出："a"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// 1 <= dictionary.length <= 1000 
// 1 <= dictionary[i].length <= 1000 
// s 和 dictionary[i] 仅由小写英文字母组成 
// 
//
// Related Topics 数组 双指针 字符串 排序 👍 325 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

//java:通过删除字母匹配到字典里最长单词
public class Q0524LongestWordInDictionaryThroughDeleting {
    public static void main(String[] args){
//        Solution solution = new Q0524LongestWordInDictionaryThroughDeleting().new Solution();
        String longestWord = new Q0524LongestWordInDictionaryThroughDeleting().new Solution().findLongestWord("aewfafwafjlwajflwajflwafj", Arrays.asList("apple","ewaf","awefawfwaf","awef","awefe","ewafeffewafewf"));
        System.out.println(longestWord);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        String res = "";
        if (s == null || s.length() < 1 || s.length() > 1000) return res;
        for (String str : dictionary) {
            int sIndex = 0, dicStrIndex= 0;
            while (sIndex < s.length() && dicStrIndex < str.length()) {
                if (s.charAt(sIndex) == str.charAt(dicStrIndex)) {
                    dicStrIndex++;
                }
                sIndex++;
            }
            // 该方法不通过
            // aewfafwafjlwajflwajflwafj"
            //			["apple","ewaf","awefawfwaf","awef","awefe","ewafeffewafewf"]
            //	测试结果:"awef"
            //	期望结果:"ewaf"
//            if (dicStrIndex == str.length()
//                    && (res.length() < str.length()
//                    || (str.length() == res.length() && str.compareTo(res) < 0)) {
//                res = str;
//            }
            if (dicStrIndex == str.length()) {
                if (res.length() < str.length()
                        || (str.length() == res.length() && str.compareTo(res) < 0)) {
                    res = str;
                }
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}